// Copyright 2012 The go-algs Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package heap implements functions for searching for integers in an array.
package search

// A basic recursive binary search function.
func BinarySearch(a []int, k, p, r int) int {
	if r > p {
		q := (p + r) / 2
		if k < a[q] {
			return BinarySearch(a, k, p, q-1)
		}
		if k > a[q] {
			return BinarySearch(a, k, q+1, r)
		}
		if k == a[q] {
			return q
		}
	}
	return -1
}

// A basic iterative binary search function.
func BinarySearchIter(a []int, k int) int {
	p := 0
	r := len(a) - 1
	for {
		if p > r {
			break
		}
		q := (p + r) / 2
		if k < a[q] {
			r = q - 1
		}
		if k > a[q] {
			p = q + 1
		}
		if k == a[q] {
			return q
		}
	}
	return -1
}

// A basic recursive binary search function for finding the first index of an
// integer.
func BinaryFindFirst(a []int, k, p, r int) int {
	if p < r {
		q := (p + r) / 2
		if k <= a[q] {
			return BinaryFindFirst(a, k, p, q)
		}
		if k > a[q] {
			return BinaryFindFirst(a, k, q+1, r)
		}
	}
	if len(a) <= p || k != a[p] {
		return -1
	}
	return p
}

// A basic recursive binary search function for finding the last index of an
// integer.
func BinaryFindLast(a []int, k, p, r int) int {
	if p < r {
		q := (p + r + 2 - 1) / 2 //ceiling
		if k < a[q] {
			return BinaryFindLast(a, k, p, q-1)
		}
		if k >= a[q] {
			return BinaryFindLast(a, k, q, r)
		}
	}
	if len(a) <= p || k != a[p] {
		return -1
	}
	return p
}

// A basic iterative binary search function for finding the first index of an
// integer.
func BinaryFindFirstIter(a []int, k int) int {
	p := 0
	r := len(a) - 1
	for {
		if p >= r {
			break
		}
		q := (p + r) / 2
		if k <= a[q] {
			r = q
			continue
		}
		if k > a[q] {
			p = q + 1
			continue
		}
	}
	if len(a) <= p || k != a[p] {
		return -1
	}
	return p
}

// A basic iterative binary search function for finding the last index of an
// integer.
func BinaryFindLastIter(a []int, k int) int {
	p := 0
	r := len(a) - 1
	for {
		if p >= r {
			break
		}
		q := (p + r + 2 - 1) / 2 // ceiling
		if k < a[q] {
			r = q - 1
			continue
		}
		if k >= a[q] {
			p = q
			continue
		}
	}
	if len(a) <= p || k != a[p] {
		return -1
	}
	return p
}

// A basic iterative binary search function for finding the first and last
// positions of a given integer to count them.
func BinaryCountIter(a []int, k int) int {
	p := 0
	r := len(a) - 1
	if r < 1 {
		return 0
	}
	for {
		if p >= r {
			break
		}
		q := (p + r) / 2
		if k <= a[q] {
			r = q
			continue
		}
		if k > a[q] {
			p = q + 1
			continue
		}
	}
	if k != a[p] {
		return 0
	}
	first := p
	r = len(a) - 1
	for {
		if p >= r {
			break
		}
		q := (p + r + 1) / 2
		if k < a[q] {
			r = q - 1
			continue
		}
		if k >= a[q] {
			p = q
			continue
		}
	}
	return p - first + 1
}
